package com.example.arithmeticleetcode.arithmetic;


/**
 * @program: arithmetic-leetcode
 * @description: 最好的情况是O(n), 最坏的情况为O(n ^ 2)
 * @author: FangZhen
 * @create: 2020-04-17 10:22
 **/
public class FastSort {

    public static void main(String[] args) {
        int[] arr = {8, 5, 3, 2};
        fastSort01(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    /**
     * 快速排序
     *
     * @param arr 要排序的数组
     * @param L   指向数组的第一个元素
     * @param R   指向数组的最后一个元素
     */
    public static void fastSort01(int[] arr, int L, int R) {
        int i = L;
        int j = R;
        int midValue = arr[(L + R) / 2];
        while (i <= j) {
            while (midValue < arr[j]) {
                j--;
            }
            while (midValue > arr[i]) {
                i++;
            }

            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }

        if (L < j) {
            fastSort01(arr, L, j);
        }

        if (i < R) {
            fastSort01(arr, i, R);
        }
    }
}